{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Replace Elements with Greatest Element on Right Side"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: replaceElements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将每个元素替换为右侧最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>arr</code> ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 <code>-1</code> 替换。</p>\n",
    "\n",
    "<p>完成所有替换操作后，请你返回这个数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [17,18,5,4,6,1]\n",
    "<strong>输出：</strong>[18,6,6,6,1,-1]\n",
    "<strong>解释：</strong>\n",
    "- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)\n",
    "- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)\n",
    "- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)\n",
    "- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)\n",
    "- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)\n",
    "- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [400]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>下标<strong> </strong>0 的元素右侧没有其他元素。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= arr[i] <= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [replace-elements-with-greatest-element-on-right-side](https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [replace-elements-with-greatest-element-on-right-side](https://leetcode.cn/problems/replace-elements-with-greatest-element-on-right-side/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[17,18,5,4,6,1]', '[400]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return [-1]\n",
    "        max_num = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            temp = max(max_num, nums[i])\n",
    "            nums[i] = max_num\n",
    "            max_num = temp\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        # 前缀和\n",
    "        res = []\n",
    "        m = -1\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            res.append(m)\n",
    "            m = max(m,arr[i])\n",
    "        \n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        maxmium = -inf\n",
    "        for i in range(n):\n",
    "            if i == n-1:\n",
    "                arr[i] = -1\n",
    "            else:\n",
    "                if arr[i] >= maxmium:\n",
    "                    arr[i] = max(arr[i+1:])\n",
    "                    maxmium = arr[i]\n",
    "                else:\n",
    "                    arr[i] = maxmium\n",
    "        return arr\n",
    "        '''\n",
    "        n = len(arr)\n",
    "        ans = [0]*(n-1)+[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            ans[i] = max(ans[i+1],arr[i+1])\n",
    "        return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        biggest = arr[-1]\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tag = arr[i]\n",
    "            arr[i] = biggest\n",
    "            if tag > biggest:\n",
    "                biggest = tag\n",
    "        arr[-1] = -1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        rightMax = -1\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            newMax = max(rightMax, arr[i])\n",
    "            arr[i] = rightMax\n",
    "            rightMax = newMax\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        if len(arr) == 1:\n",
    "            return [-1]\n",
    "        mx = max(arr[1:])\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i] == mx:\n",
    "                mx = max(arr[i+1:])\n",
    "            arr[i] = mx\n",
    "        arr[-1] = -1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        tmax=-1\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            arr[i],tmax=tmax,max(arr[i],tmax)         \n",
    "        return arr\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        m=arr[-1]\n",
    "        i=len(arr)-1\n",
    "        while i>=0:\n",
    "            if arr[i]>m:\n",
    "                arr[i],m=m,arr[i]\n",
    "            else:\n",
    "                arr[i]=m\n",
    "            i=i-1\n",
    "        arr[-1]=-1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        r_maxnum = arr[-1]\n",
    "        arr[-1] = -1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            temp = arr[i]\n",
    "            arr[i] = r_maxnum\n",
    "            r_maxnum = max(r_maxnum, temp)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        maxvalue = arr[0]\n",
    "        for i in range(0, len(arr)):\n",
    "            # print(arr[i + 1:])\n",
    "            if i == len(arr) - 1:\n",
    "                arr[i] = -1\n",
    "            else:\n",
    "                if arr[i] == maxvalue:\n",
    "                    maxvalue = max(arr[i + 1:])\n",
    "                    arr[i] = max(arr[i + 1:])\n",
    "                else:\n",
    "                    arr[i] = maxvalue\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 往回頭比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        \"\"\"\n",
    "        1. 題目要求的是 \"除了自己\" 的右邊, 找最大值\n",
    "        2. 對於 arr 最後一個元素: arr[-1] 而言, 它一定會被換成 -1\n",
    "           所以我們從 arr[-2] 開始看起\n",
    "\n",
    "            a. result[-1] 一定是 -1\n",
    "            b. result[-2] 一定是 arr[-1] 和 \"-1\" 做比較, 找出最大值\n",
    "               result[-2] = max(result[-1], arr[-1])\n",
    "\n",
    "            c. result[-3] = max(result[-2], arr[-2])\n",
    "            由於已經找出了 result[-2]: 範圍的最大值(包含 result[-2:-1])\n",
    "            再往前面走一格, 拿 arr[-2] 和 result[-2] 比誰是最大值 \n",
    "            在這個狀況下只要比兩個數字就好了\n",
    "        \"\"\"\n",
    "\n",
    "        # 聽了 neetcode 前半段的寫法\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 這樣寫也可以，結果會出錯\n",
    "        \"\"\"\n",
    "        result = [-1]\n",
    "        for n in reversed(arr[1:]):\n",
    "            result.append(max(result[-1], n))\n",
    "        return reversed(result)\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法:\n",
    "        # mem: O(1)\n",
    "        old_max = -1\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            new_max = max(old_max, arr[i])\n",
    "            arr[i]  = old_max\n",
    "            old_max = new_max\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        max_val = -1\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            a = arr[i]\n",
    "            arr[i] = max_val\n",
    "            max_val = max(max_val, a)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        cur_max = arr[-1]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            tmp = arr[i]\n",
    "            arr[i] = cur_max\n",
    "            cur_max = max(cur_max, arr[i], tmp)\n",
    "\n",
    "        arr[-1] = -1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        m,n=0,0\n",
    "        for i in range(len(arr)-1):\n",
    "            if i<n:\n",
    "                arr[i]=m\n",
    "            else:\n",
    "                m=max(arr[i+1:len(arr)])\n",
    "                n=arr[i+1:len(arr)].index(m)\n",
    "                arr[i]=m\n",
    "        arr[-1]=-1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        left_max = arr[:]\n",
    "        left_max[-1] = -1\n",
    "        temp_max = arr[-1]\n",
    "        for i in reversed(range(len(arr) - 1)):\n",
    "            left_max[i] = temp_max\n",
    "            temp_max = max(temp_max, arr[i])\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = left_max[i]\n",
    "\n",
    "        # arr[-1] = -1\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        tmp=-1\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            cur=arr[i]\n",
    "            arr[i]=tmp\n",
    "            tmp=max(cur,tmp)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        maxNum = -1\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            arr[i], maxNum = maxNum, max(maxNum, arr[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        b=arr[-1]\n",
    "        arr[-1]=-1\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            arr[i],b=b,max(b,arr[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        m =-1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            tmp = arr[i]\n",
    "            arr[i] = m \n",
    "            m = max(tmp,m)\n",
    "            \n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        # we define the right_most one\n",
    "        right_most = -1\n",
    "\n",
    "        # this starts from the last one in the list to the 1st one, the order is from behind so we use -1\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            # newMax = max(right_most, the oringinal value of arr [i])\n",
    "            newMax = max(right_most, arr[i])\n",
    "            # now we can change the value of arr[i]\n",
    "            arr[i] = right_most\n",
    "            # so we will get the right_most of the next i\n",
    "            right_most = newMax\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n, m = len(arr), -1 # m 记录最大值\n",
    "        for i in range(n - 1, -1, -1): # 逆序遍历\n",
    "            m, arr[i] = max(arr[i], m), m # 原地修改，可定义列表。\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            t = arr[i]\n",
    "            arr[i] = ans\n",
    "            ans = max(ans, t)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        rMax = -1\n",
    "        index = len(arr) - 1\n",
    "        while index >= 0:\n",
    "            tmp = arr[index]\n",
    "            arr[index] = rMax\n",
    "            rMax = max(rMax, tmp)\n",
    "            index -= 1\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        m = -1\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            a = arr[i]\n",
    "            arr[i] = m\n",
    "            if a > m:\n",
    "                m = a\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        biggest = arr[-1]\n",
    "        n = len(arr)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tag = arr[i]\n",
    "            arr[i] = biggest\n",
    "            if tag > biggest:\n",
    "                biggest = tag\n",
    "        arr[-1] = -1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        b=arr[-1]\n",
    "        arr[-1]=-1\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            arr[i],b=b,max(b,arr[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        mx = -1\n",
    "        n = len(arr)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            tmp = arr[i]\n",
    "            arr[i] = mx\n",
    "            mx = max(mx,tmp)\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == n-1:\n",
    "                res[i] = -1\n",
    "            else:\n",
    "                res[i] = max(arr[i+1], res[i+1])\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 往回頭比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        \"\"\"\n",
    "        1. 題目要求的是 \"除了自己\" 的右邊, 找最大值\n",
    "        2. 對於 arr 最後一個元素: arr[-1] 而言, 它一定會被換成 -1\n",
    "           所以我們從 arr[-2] 開始看起\n",
    "\n",
    "            a. result[-1] 一定是 -1\n",
    "            b. 而 result[-2] 一定是 arr[-1] 和 -1 做比較, 找出最大值\n",
    "            result[-2] = max(result[-1], arr[-1])\n",
    "\n",
    "            由於已經找出了 result[-2]: 範圍的最大值(包含 result[-2:-1])\n",
    "            再往前面走一格, 拿 arr[-2] 和 result[-2] 比誰是最大值 \n",
    "            在這個狀況下只要比兩個數字就好了\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: list[int]) -> list[int]:\n",
    "        n = len(arr)\n",
    "        # initialize the max_right to record the max element to the right\n",
    "        max_right = -1\n",
    "\n",
    "        # traverse the array from the right to the left\n",
    "        for i in range(n-1, -1, -1):\n",
    "            cur_element = arr[i]\n",
    "            arr[i] = max_right\n",
    "            max_right = max(max_right, cur_element)\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        b=arr[-1]\n",
    "        arr[-1]=-1\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            arr[i],b=b,max(b,arr[i])\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        maxnow = -1\n",
    "        for pos in range(len(arr) - 1, -1, -1):\n",
    "            temp = arr[pos]\n",
    "            arr[pos] = maxnow\n",
    "            maxnow = max(maxnow, temp)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 往回頭比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        \"\"\"\n",
    "        1. 題目要求的是 \"除了自己\" 的右邊, 找最大值\n",
    "        2. 對於 arr 最後一個元素: arr[-1] 而言, 它一定會被換成 -1\n",
    "           所以我們從 arr[-2] 開始看起\n",
    "\n",
    "            a. result[-1] 一定是 -1\n",
    "            b. result[-2] 一定是 arr[-1] 和 \"-1\" 做比較, 找出最大值\n",
    "               result[-2] = max(result[-1], arr[-1])\n",
    "\n",
    "            c. result[-3] = max(result[-2], arr[-2])\n",
    "            由於已經找出了 result[-2]: 範圍的最大值(包含 result[-2:-1])\n",
    "            再往前面走一格, 拿 arr[-2] 和 result[-2] 比誰是最大值 \n",
    "            在這個狀況下只要比兩個數字就好了\n",
    "        \"\"\"\n",
    "\n",
    "        # 聽了 neetcode 前半段的寫法: mem: O(n)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 這樣寫也可以，但結果會報錯\n",
    "        \"\"\"\n",
    "        result = [-1]\n",
    "        for n in reversed(arr[1:]):\n",
    "            result.append(max(result[-1], n))\n",
    "        return reversed(result)\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: mem: O(1)\n",
    "        old_max = -1\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            new_max = max(old_max, arr[i])\n",
    "            arr[i]  = old_max\n",
    "            old_max = new_max\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [-1] * n\n",
    "        cur_max = 0\n",
    "        # 倒序\n",
    "        for i in range(n-1, 0, -1):\n",
    "            cur_max = max(cur_max, arr[i])\n",
    "            ans[i-1] = cur_max\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res = [-1]*len(arr)\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            #print(res[i],res[i+1],arr[i+1])\n",
    "            res[i] = max(res[i+1],arr[i+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        a=len(arr)\n",
    "        ans=[0]*(a-1)+[-1]\n",
    "        for i in range(len(ans)-2,-1,-1):\n",
    "            ans[i]=max(ans[i+1],arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * (n - 1) + [-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i + 1], arr[i + 1])\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        max_ = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i == n-1:\n",
    "                max_[i] = -1\n",
    "                maxt = arr[i]\n",
    "            else:\n",
    "                max_[i] = maxt\n",
    "                maxt = max(maxt, arr[i])\n",
    "        for i in range(n):\n",
    "            arr[i] = max_[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res = [-1]*len(arr)\n",
    "        tmp = -9999\n",
    "        for i in range(len(arr)-1):\n",
    "            if arr[i]<tmp:\n",
    "                res[i]=tmp\n",
    "                continue\n",
    "            tmp = -9999\n",
    "            for j in range(i+1,len(arr)):\n",
    "                if arr[j]>tmp:\n",
    "                    tmp=arr[j]\n",
    "            res[i]=tmp\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        res = [0] * n\n",
    "        idx = 0\n",
    "        m = max(arr)\n",
    "        for i in range(n-1):\n",
    "            if arr[i] != m:\n",
    "                res[i] = m\n",
    "            else:\n",
    "                m = max(arr[i+1:])\n",
    "                res[i] = m\n",
    "        res[-1] = -1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        post_max = [-1 for i in range(len(arr))]\n",
    "        post_max[len(arr)-1] = arr[len(arr)-1]\n",
    "        for i in range(len(arr) - 2, 0, -1):\n",
    "            post_max[i] = max(arr[i], post_max[i + 1])\n",
    "        for i in range(len(arr)-1):\n",
    "            arr[i] = post_max[i+1]\n",
    "        arr[-1] = -1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        ans = [0] * (len(arr)-1) + [-1]\n",
    "        for i in range(len(arr)-2, -1, -1):\n",
    "            if i != len(arr) - 1:\n",
    "                ans[i] = max(ans[i+1], arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        result=[-1]*len(arr)\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            result[i]=max(result[i+1],arr[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        temp = [None]*len(arr)\n",
    "        max1 = 0\n",
    "        for i in range(len(arr)-1,-1,-1):\n",
    "            if arr[i]>max1:\n",
    "                max1 = arr[i]\n",
    "                temp[i] = max1\n",
    "            else:\n",
    "                temp[i] = max1\n",
    "        return temp[1:]+[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * (n - 1) + [-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i + 1], arr[i + 1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [-1] * n\n",
    "        cur_max = arr[-1]\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = cur_max\n",
    "            cur_max = max(cur_max, arr[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0]*(n-1) + [-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            ans[i] = max(ans[i+1], arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        result=[-1]*len(arr)\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            result[i]=max(result[i+1],arr[i+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 反過來比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def replaceElements(self, arr: list[int]) -> list[int]:\r\n",
    "        if len(arr) == 1:\r\n",
    "            return [-1]\r\n",
    "        arr_2 = [-1] * len(arr)\r\n",
    "        for i in range(2, len(arr) + 1):\r\n",
    "            p = -1 * i\r\n",
    "            if arr[p + 1] > arr_2[p + 1]:\r\n",
    "                arr_2[p] = arr[p + 1]\r\n",
    "            else:\r\n",
    "                arr_2[p] = arr_2[p + 1]\r\n",
    "        return arr_2\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        arr=arr[::-1]\n",
    "        a=0\n",
    "        for i,x in enumerate(arr):\n",
    "            if x>a:\n",
    "                a=x\n",
    "            arr[i]=a\n",
    "\n",
    "        arr=arr[::-1]\n",
    "        arr=arr[1:]+[-1]\n",
    "        return arr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * (n - 1) + [-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i + 1], arr[i + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [-1] * n\n",
    "        stack = [arr[-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            ans[i] = stack[-1]\n",
    "            if arr[i] >= stack[-1]:\n",
    "                stack.append(arr[i])            \n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 反過來做\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        1.划分为两个阶段 左边和右边\n",
    "          左边是自己，右边中查找到最大的那个数字进行交换\n",
    "        2.遇到右边的长度为0时候，左边就是自己的这个元素的数值改为-1\n",
    "        \"\"\"\n",
    "        lens = len(arr)\n",
    "\n",
    "        new = [-1]*lens\n",
    "      \n",
    "        for i in range(lens - 2, -1, -1):\n",
    "           new[i] = max(arr[i+1], new[i+1])\n",
    "\n",
    "        return new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "\n",
    "        res = [0] * n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if i == n-1:\n",
    "                res[i] = -1\n",
    "            else:\n",
    "                res[i] = max(arr[i+1], res[i+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        ans =[0]*(n-1)+[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            ans[i] =max(ans[i+1],arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        a=[0]*(len(arr))\n",
    "        a[-1]=-1\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            a[i]=max(a[i+1],arr[i+1])\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        ans=[0]*(n-1)+[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            ans[i]=max(ans[i+1],arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * (n - 1) + [-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i + 1], arr[i + 1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0]*(n-1) + [-1]\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            ans[i] = max(arr[i+1], ans[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res = [-1] * len(arr)\n",
    "        maximum = arr[-1]\n",
    "        for i in range(len(arr)-1, 0, -1):\n",
    "            maximum = max(maximum, arr[i])\n",
    "            res[i-1] = maximum\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans = [0] * (n-1) + [-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            ans[i] = max(ans[i+1], arr[i+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res = [0]*(len(arr)-1) + [-1]\n",
    "        for i in range(len(arr)-2,-1,-1):\n",
    "            res[i] = max(arr[i+1],res[i+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        def zui(na):\n",
    "            ma = max(na[1:])\n",
    "            ima = len(na)-na[::-1].index(ma)-1\n",
    "            na1 = [ma]*ima\n",
    "            na = na[ima:]\n",
    "            return na1,na\n",
    "        l = []\n",
    "        while len(arr) != 1:\n",
    "            arr1,arr = zui(arr)\n",
    "            l = l+arr1\n",
    "        l.append(-1)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        mx = -1\n",
    "        ans = []\n",
    "        for num in arr[::-1]:\n",
    "            ans.append(mx)\n",
    "            mx = max(mx, num)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n,ans = -1,[]\n",
    "        for i in arr[::-1]:\n",
    "            ans.append(n)\n",
    "            if i > n:\n",
    "                n = i \n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        res = []\n",
    "\n",
    "        max_value = -1\n",
    "\n",
    "        for num in arr[::-1]:\n",
    "            res.append(max_value)\n",
    "            max_value = max(max_value, num)                \n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        pre = -1\n",
    "        res = []\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            res.append(pre)\n",
    "            pre = max(pre, arr[i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        max_number = -1\n",
    "        while arr:\n",
    "            number = arr.pop(-1)\n",
    "            res.append(max_number)\n",
    "            if number>max_number:\n",
    "                max_number = number\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        temp, ans, i = -1, [], len(arr) - 1\n",
    "        while i > -1:\n",
    "            ans.append(temp)\n",
    "            if arr[i] > temp:\n",
    "                temp = arr[i]\n",
    "            i -= 1\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        ans = [-1, ]\n",
    "        m = arr[-1]\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            ans.insert(0, m)\n",
    "            m = max(m, arr[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        arr_len=len(arr)\n",
    "        ans = [-1]\n",
    "        for i in range(arr_len-1,0,-1):\n",
    "            ans.append(max(ans[-1],arr[i]))\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n,ans = -1,[]\n",
    "        for i in arr[::-1]:\n",
    "            ans.insert(0,n)\n",
    "            if i > n:\n",
    "                n = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        mx=-1\n",
    "        for x in reversed(arr):\n",
    "            res.append(mx)\n",
    "            mx=max(mx,x)\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        ma=arr[-1]\n",
    "        for i in range(len(arr)-1,0,-1):\n",
    "            if arr[i]>ma:\n",
    "                ma=arr[i]\n",
    "            res.append(ma)\n",
    "        res=res[::-1]\n",
    "        res.append(-1)\n",
    "        return res\n",
    "\n",
    "        # for i in range(len(arr)-1):\n",
    "        #     arr[i]=max(arr[i+1:])\n",
    "        # arr[-1]=-1\n",
    "        # return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        res = [-1]\n",
    "        max_value = arr[-1]\n",
    "        for ii in range(len(arr) - 1, 0, -1):\n",
    "            max_value = max(max_value, arr[ii])\n",
    "            res.append(max_value)\n",
    "        \n",
    "        print(res)\n",
    "        res.reverse()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return [-1]\n",
    "\n",
    "        res = [-1]\n",
    "        maxV = arr[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            res.append(maxV)\n",
    "            if arr[i]>maxV:\n",
    "                maxV = arr[i]\n",
    "        res.reverse()\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        return list(accumulate(arr[:0:-1], max))[::-1] + [-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
